package com.wfm.leetcode.editor.cn;

import java.util.PriorityQueue;
import java.util.TreeMap;

/**
 * 数据流的中位数
 * 2024-04-08 15:56:12
 * 方法一： 优先队列
 * 小 queMax
 * 大 queMin
 * 新来一个数，如果大顶堆为空||数比大顶堆的小，则先加入大顶堆里，
 * 比如来2，因为大顶堆为空，则加入
 * 小 queMax
 * 大 queMin 2
 * 来个-1 比2小，还是加入大顶堆
 * 小 queMax
 * 大 queMin -1 2
 * 这个时候要判断打顶堆和小顶堆的长度差距，小只能比大差1，现在差2，所以要把大顶堆的数移动到小
 * 小 queMax 2
 * 大 queMin -1
 * 如果来个3，比大顶堆的大了，那么直接加入小顶堆
 * 小 queMax 3 2
 * 大 queMin -1
 * 加完后也要判断，发现小顶堆的长度居然更长，所以要把3 移到大顶堆
 * 小 queMax 3
 * 大 queMin -1 2
 * 中位数就是，如果两个长度一样，取两个堆顶/2
 * 如果大更长，则大顶堆的数就是中位数
 * O(logn) O(n)
 */
class FindMedianFromDataStream {

    //leetcode submit region begin(Prohibit modification and deletion)
    class MedianFinder {
        PriorityQueue<Integer> queMax;//小顶堆，保存大于中位数的
        PriorityQueue<Integer> queMin;//大顶堆，保存小于等于中位数的

        public MedianFinder() {
            queMax = new PriorityQueue<>();
            queMin = new PriorityQueue<>((a, b) -> (b - a));
        }

        public void addNum(int num) {
            if (queMin.isEmpty() || num < queMin.peek()) {
                queMin.add(num);
                if (queMin.size() > queMax.size() + 1) {
                    queMax.add(queMin.poll());
                }
            } else {
                queMax.add(num);
                if (queMax.size() > queMin.size()) {
                    queMin.add(queMax.poll());
                }
            }
        }

        public double findMedian() {
            if (queMin.size() == queMax.size()) {
                return (queMin.peek() + queMax.peek()) / 2.0;
            } else {
                return queMin.peek();
            }
        }
    }

    /**
     * Your MedianFinder object will be instantiated and called as such:
     * MedianFinder obj = new MedianFinder();
     * obj.addNum(num);
     * double param_2 = obj.findMedian();
     */
//leetcode submit region end(Prohibit modification and deletion)
    class MedianFinder1 {
        TreeMap<Integer, Integer> nums;
        int n;
        int[] left;
        int[] right;

        public MedianFinder1() {
            nums = new TreeMap<Integer, Integer>();
            n = 0;
            left = new int[2];
            right = new int[2];
        }

        public void addNum(int num) {
            nums.put(num, nums.getOrDefault(num, 0) + 1);
            if (n == 0) {
                left[0] = right[0] = num;
                left[1] = right[1] = 1;
            } else if ((n & 1) != 0) {
                if (num < left[0]) {
                    decrease(left);
                } else {
                    increase(right);
                }
            } else {
                if (num > left[0] && num < right[0]) {
                    increase(left);
                    decrease(right);
                } else if (num >= right[0]) {
                    increase(left);
                } else {
                    decrease(right);
                    System.arraycopy(right, 0, left, 0, 2);
                }
            }
            n++;
        }

        public double findMedian() {
            return (left[0] + right[0]) / 2.0;
        }

        private void increase(int[] iterator) {
            iterator[1]++;
            if (iterator[1] > nums.get(iterator[0])) {
                iterator[0] = nums.ceilingKey(iterator[0] + 1);
                iterator[1] = 1;
            }
        }

        private void decrease(int[] iterator) {
            iterator[1]--;
            if (iterator[1] == 0) {
                iterator[0] = nums.floorKey(iterator[0] - 1);
                iterator[1] = nums.get(iterator[0]);
            }
        }
    }

    public static void main(String[] args) {
        MedianFinder1 solution = new FindMedianFromDataStream().new MedianFinder1();
        solution.addNum(2);
        solution.addNum(3);
        solution.addNum(4);
        solution.addNum(-1);
        solution.addNum(-2);
    }
}